﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace www.coursera.algo.org._3.ClosePoint1D
{
    class Program
    {
        static void Main(string[] args)
        {
            Random randomGen = new Random();
            Stopwatch sw = new Stopwatch();
		    List<Point> points = new List<Point>();
            
		    for (int i=0; i<8000; i++)
		    {
		        int tempX = randomGen.Next(0, 50000);
                if (!points.Exists(p => p.X == tempX))
                    points.Add(new Point(tempX));
		    }
            //printList(points);
            
            
            points=MergeSorter.Sort(points);
            

            //printList(points);


            sw.Start();
            var temp = findClosestPairBF(points.ToArray());
            sw.Stop();
            Console.WriteLine("Total calculation time: {0}", sw.Elapsed);
            printList(temp.ToList());
            Console.WriteLine("-------------------------Done-----------------------");

            sw.Reset();
            sw.Start();
            int delta;
            ReturnData temp1 = findClosestPairDC(points.ToArray());
            sw.Stop();
            Console.WriteLine("Total calculation time: {0}", sw.Elapsed);
            Console.WriteLine(temp1.Delta);
            Console.WriteLine(temp1.A.X);
            Console.WriteLine(temp1.B.X);
            

            //printList(temp.ToList());


            Console.ReadLine();
        }


        static Point[] findClosestPairBF(Point[] points)
        {
            Point[] closestPair = new Point[2];

            double minDistance = points[0].distance(points[1]); //assumes first 2 elements are
            closestPair[0] = points[0];
            closestPair[1] = points[1];
            //closest pair
            for (int i = 0; i < points.Length - 1; i++)
            {
                if (points[i].distance(points[i + 1]) < minDistance)
                {
                    minDistance = points[i].distance(points[i + 1]);
                    Point min1 = new Point(points[i].X);
                    Point min2 = new Point(points[i + 1].X);
                    closestPair[0] = min1;
                    closestPair[1] = min2;
                    //If it finds a smaller distance, it creates 2 points and places them
                    //into the closestPair array
                }
            }

            return closestPair;
        }

        static ReturnData findClosestPairDC(Point[] points)
	{
		int median;
        ReturnData data = new ReturnData();
		Point[] points1, points2;
        if (points.Length <= 2)
        {
            data.Delta = 100000000;
            
            return data;
        }
        else if(points.Length <=2)
		{
            
		    data.Delta = Math.Abs(points[1].X - points[0].X);
		    data.A = points[1];
            data.B= points[0];
            return data;
		}
            
		else{
		        median = points.Length/2;
			if(points.Length%2 == 1)	//Checks for odd number of elements
			{
				points1 = new Point[median];
				points2 = new Point[median+1];
				for(int i=0;i<median;i++)
					points1[i] = points[i];
			   
				for (int i=median;i<points.Length; i++)

				{
                    points2[i-median] = points[i];
				    
				}
			    
			}
			else{
				 points1 = new Point[median];
				 points2 = new Point[median];
				
				for(int i=0; i<median; i++)
					points1[i] = points[i];
			    
				for (int i=median; i<points.Length; i++)
				{
                    points2[i - median] = points[i];
				    
				}
			    
			}
		    int deltaL, deltaR;
            ReturnData minLeft = findClosestPairDC(points1);
            ReturnData minRight = findClosestPairDC(points2);
            int delta = Math.Min(minLeft.Delta, minRight.Delta);
            
            if (Math.Abs(points2.First().X - points1.Last().X) < delta)
            {
                data.Delta = Math.Abs(points2.First().X - points1.Last().X);
                data.A = points1.Last();
                data.B = points2.First();
            }
            else if (minLeft.Delta < minRight.Delta)
            {
                data = minLeft;
            }
            else
            {
                data = minRight;
            }
			
		}

        return data;
	}



        


        


        private static void printList(List<Point> list)
        {

            foreach (var t in list)
            {
                if(t!=null)
                Console.Write(t.X + " ");
            }
            Console.WriteLine();

        }
		    
		
		
		
        



        
    }

    public class Point : IComparable
    {
        public int X { get; private set; }

        public Point(int number)
        {
            this.X = number;
        }


        public int distance(Point point)
        {
            return Math.Abs(point.X - this.X);
        }

        #region Implementation of IComparable

        /// <summary>
        /// Compares the current instance with another object of the same type and returns an integer that indicates whether the current instance precedes, follows, or occurs in the same position in the sort order as the other object.
        /// </summary>
        /// <returns>
        /// A value that indicates the relative order of the objects being compared. The return value has these meanings: Value Meaning Less than zero This instance is less than <paramref name="obj"/>. Zero This instance is equal to <paramref name="obj"/>. Greater than zero This instance is greater than <paramref name="obj"/>. 
        /// </returns>
        /// <param name="obj">An object to compare with this instance. </param><exception cref="T:System.ArgumentException"><paramref name="obj"/> is not the same type as this instance. </exception><filterpriority>2</filterpriority>
        public int CompareTo(object other)
        {
            var temp = (Point) other;
            return temp.X.CompareTo(this.X);
        }

        #endregion
    }
    
    public class ReturnData
    {
        public Point A;
        public Point B;
        public int Delta;
    }


}
